package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.HashSet;
import java.util.Set;

/**
 * 查找图的割点
 *
 * @author initcap
 * @date Created in 2020/1/31 16:29.
 */
public class FindCutPoints {

    private Graph<Integer, Integer> graph;
    private Set<Integer> cutpoints;
    private boolean[] visited;
    private int[] ord;
    private int[] low;
    private int cnt;

    public FindCutPoints(Graph graph) {
        this.graph = graph;
        cutpoints = new HashSet<>();
        visited = new boolean[graph.nodeSize()];
        ord = new int[graph.nodeSize()];
        low = new int[graph.nodeSize()];
        cnt = 0;
        for (int i = 0; i < graph.nodeSize(); i++) {
            if (!visited[i]) {
                dfs(i, i);
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new SparseGraph("algorithm/testG11.txt", false);
        Set<Integer> res = new FindCutPoints(g).result();
        System.out.println(res);
    }

    private void dfs(int node, int parent) {
        visited[node] = true;
        ord[node] = cnt;
        low[node] = ord[node];
        cnt++;

        int child = 0;
        for (Integer w : graph.adj(node)) {
            if (!visited[w]) {
                dfs(w, node);
                low[node] = Math.min(low[w], low[node]);
                // 判断割点的两种情况
                if (node != parent && low[w] >= ord[node]) {
                    cutpoints.add(node);
                }

                child++;
                if (child > 1 && node == parent) {
                    cutpoints.add(node);
                }
            } else {
                if (w != parent) {
                    low[node] = Math.min(low[w], low[node]);
                }
            }
        }
    }

    public Set<Integer> result() {
        return cutpoints;
    }
}
